package edu.cmu.cs211.pg.algorithms;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import edu.cmu.cs211.pg.graph.Edge;
import edu.cmu.cs211.pg.graph.Graph;
import edu.cmu.cs211.pg.graph.Path;
import edu.cmu.cs211.pg.graph.WeightedEdge;

public class Dijkstra
{
        /**
         * Returns the shortest path on the given graph using Dijkstra's Algorithm
         * In this case, shortest path is defined as the path for which the total weight is minimized
         * 
         * @param g The graph that we are searching for a path on
         * @param start The vertex that begins the path
         * @param goal The vertex we are trying to find a path to
         * @throws IllegalArgumentException if either start or goal is not a vertex in g  
         * @throws IllegalArgumentException
         *             if g has negative edge weights.
         * @return A list of Edges that represent a path between start and goal if one exists
         *            Otherwise, returns null
         */
	
		/*
		 * Assign to every node a distance value. Set it to zero for our initial
		 *  node and to infinity for all other nodes.
		 *  Mark all nodes as unvisited. Set initial node as current.
		 *  For current node, consider all its unvisited neighbours and calculate 
		 *  their distance (from the initial node). 
		 *  When we are done considering all neighbours of the current node, 
		 *  mark it as visited. A visited node will not be checked ever again; 
		 *  its distance recorded now is final and minimal.
		 *  Set the unvisited node with the smallest distance (from 
		 *  the initial node) as the next "current node" and continue.
		 */
        public <V extends Comparable<V>,E extends WeightedEdge<V>> Path<V,E> shortestPath(Graph<V,E> g, V start, V goal)
        {
        	/*
        	 * make sure no illegal arguments are passed
        	 */
            if(g.vertices().contains(start) != true || g.vertices().contains(goal) != true)
                throw new IllegalArgumentException();
            
            Set<V> verts = g.vertices();
            Iterator<V> it2 = verts.iterator();
            while (it2.hasNext()) {
                Set<E> ed = g.outgoingEdges(it2.next());
                Iterator<E> edIt = ed.iterator();
                while(edIt.hasNext()) {
                    if(( edIt.next()).weight() < 0) throw new IllegalArgumentException();
                }
            }
            
            
            /*
             * create a map and update all the WeightedEdges
             */
            Map<V,Path<V,E>> map = new TreeMap<V,Path<V,E>>();
            PriorityQueue<Path<V,E>> q = new PriorityQueue<Path<V,E>>();
            
            Path<V,E> path = new Path<V,E>(start);
            map.put(path.dest(), path);
            q.add(path);
               
            Set<V> vertices = g.vertices();
            Iterator<V> itr = vertices.iterator();
            
            while(!q.isEmpty()){
            	 Path<V,E> cur = q.poll();
            	 //you found the goal, its the shorted path
            	 if( goal != null && cur.dest().equals(goal) )
                 {
                                return map.get(cur.dest());
                 }
            	 for( E e : g.outgoingEdges(cur.dest()) )
                 {
            		 if((e.weight()) < 0) throw new IllegalArgumentException();
                     if(!map.containsKey(e.dest())){
                    	 map.put(e.dest(), cur.cons(e));//map.get(e.src()).cons(e));
                    	 q.add(map.get(e.dest()));
                     }
                     else{
                        int newDistance = cur.pathWeight() + e.weight();
                        if( newDistance < map.get(e.dest()).pathWeight() )
                         {
                    	    q.remove(map.get(e.dest()));
                        	map.put(e.dest(), cur.cons(e));
                        	q.add(map.get(e.dest()));
                    	   
                         }
                     }
                 }
            }

            return null;

        }

    /**
     * Returns the shortest path on the given graph from start to all nodes using Dijkstra's Algorithm
     * In this case, shortest path is defined as the path for which the total weight is minimized
     * 
     * NOTE: This method is NOT unit tested, but will be helpful to you in the last part!
     * 
     * @param g The graph that we are searching for paths
     * @param start The vertex that begins the path
     * @throws IllegalArgumentException if start is not a vertex in g  
     * @throws IllegalArgumentException
     *             if g has negative edge weights
     * @return A mapping from all vertices v to lists of paths that begin at start and end at v
     *               if a path from start to v exists
     *               otherwise, that mapping should be null
     */
    public <V extends Comparable<V>,E extends WeightedEdge<V>> Map<V,Path<V,E>> allShortestPaths(Graph<V,E> g, V start)
    {
        if(g.vertices().contains(start)!=true)
            throw new IllegalArgumentException();

        Map<V,Path<V,E>> map=new HashMap<V,Path<V,E>>();
        //MORE STUFF HERE!!!
        return map;
    }
}
